1. Field of The Invention
The subject invention relates to a method and apparatus for decoding statistically encoded bit streams consisting of words having variable bit lengths.
Variable-length coding is a coding technique often used for lossless data compression. In accordance with this technique, fixed-length data is converted into variable-length codewords according to the statistics of the data. In general, the lengths of the codewords are chosen so that shorter codewords are used to represent the more frequently occurring data and longer codewords are chosen to represent the less frequently occurring data. By properly assigning the variable-length codewords to the library of all possible source codewords, the averaged word-length of the variable-length codewords is shorter than that of the original data and, therefore, data compression is achieved. The Huffman code design is a procedure commonly used to construct a minimum redundant variable-length code for a known data statistic. Generally, the encoding process can be implemented by a table look-up process using the input data to address the table. The codewords and word lengths are stored as table contents, and the codewords are outputted sequentially, through a buffer, at a constant data rate onto the data channel. At the receiving end, however, the decoding process is more complicated. Due to the variable-length nature, each codeword has to be segmented from the received bit stream before it can be decoded into a source symbol. Therefore, the design of a variable-length decoder is always more difficult than the design of a variable-length encoder.
2. Description of the Related Art
There are several methods to decode a sequence of variable-length code words. The most important ones are the tree searching algorithm and the table look-up technique.
A variable-length code can always be represented by a tree with codewords as leaves (also called terminal nodes). The decoding starts from the root of the code tree and is guided by the received bit stream to follow one of two branches at each node. When a leaf is reached, the end of a codeword is detected and it is segmented from the remaining string. This type of decoder includes logic circuitry corresponding to the tree and control circuitry to traverse the code tree. This approach may be slow, especially for long codewords, since a bit-by-bit search through the code tree is required for each decoded symbol. In typical applications, an input symbol is represented by several bits. The speed of shifting received bits into a decoder is several times as high as the averaged speed of decoded data. Therefore, the tree searching-based decoder has to be operated at the speed of several times the output data rate.
Such high speed requirements are particularly critical for the digital transmission of high definition television (HDTV) signals. In such an HDTV system, the total sample rate (combined luminance and chrominance signals) is likely to be 100 MHz.
A table look-up technique is an alternative to the bit-by-bit search approach. In a table look-up technique, the received bit stream is compared with the contents of a codeword table. The codeword table has an entry associated with each possible variable-length codeword that includes the decoded fixed-length word and the length of the variable-length word. When the sequence of leading bits in an input register matches one of the entries in the codeword table, a codeword match is indicated. The input register is then shifted by the number of bits indicated by the code-length entry, thereby making the next sequence of bit available for comparison with entries in the codeword table. Disadvantageously, bit-by-bit shifting at the very high speed multiple of the sample rate is required to enable the decoder to maintain the sample rate of decoding.
A high-speed flexible variable-length-code decoder of the table look-up type includes a barrel shifter that provides an output decoding window having a bit-width equal to the maximum length codeword. In response to a control signal, the barrel shifter directly shifts its decoding window across a sequence of available input bits as each codeword is detected. The decoding window is shifted after each codeword is decoded by the number of bits corresponding to the length of the last decoded codeword. The table look-up decoder is capable of decoding at the symbol rate regardless of the word-length.
U.S. Pat. No. 5,173,695 to Sun et al., discloses a table look-up decoder of the above type. However, its actual speed of operation is limited by the propagation delay through the feedback loop consisting of the barrel shifter, the word-length decoder and the adder. The word-length decoder represents the most complex, and therefore, the slowest part of the path. In MPEG-2 applications, for example, there are multiple tables corresponding to particular types of codewords, which are not only complex by themselves, but their multiplexing and, sometimes, use of arithmetic operations, are required before the result of proper length computation is delivered to the adder.
In current implementations, the systems are normally partitioned into multiple processing paths, the variable-length decoder being one of the major bottlenecks. Since multiple variable-length decoders cannot access the rate buffer directly, multiple dedicated ping-pong buffers are normally implemented between all the variable-length decoders and the rate buffer, increasing the amount of the bit stream memory required for the system. For example, the system implemented in 8 partitions requires 8 ping-pong buffers, each one of these buffers having twice the size of the rate buffer, thereby increasing the amount of buffer memory by the factor of 16. For the duration of the picture, each one of these ping-pong buffers reads the picture partition designated for decoding by its variable-length decoder in the next picture cycle while the variable-length decoder is decoding the portion of the bit stream stored in the other bank of the ping-pong buffer.
Co-pending U.S. patent application Ser. No. 08/565,773, filed concurrently with the subject application, by Applicant, entitled "HIGH-SPEED VARIABLE-LENGTH DECODER ARRANGEMENT" (1504-1035), discloses a variable-length decoder arrangement in which speed enhancement is achieved by tagging the bit stream before the rate buffer with the codeword boundary information and by replacing the slowest part of the critical length decoding loop with a simple codeword-type-independent fixed look-up table decoder, or eliminating this loop altogether.
As in the prior art, a look-up table decoder with a barrel shifter is used. However, the subject invention takes advantage of the fact that the lengths of the codewords can be easily determined before the bit stream is entered into the rate buffer. The variable-length decoder used after the rate buffer has to be able to decode codewords at very high peak rates since, for the actual display time of the picture, it may have to extract the whole picture from the rate buffer, which may have even more codewords than there are samples in the picture. This problem is especially severe in HDTV applications where the amount of information passed through the decoding circuits is very high.
It should be understood that the variable-length decoder may be used in front of a buffer, at which point such a demanding peak codeword rate requirement does not exist. As such, the variable-length decoder may run at a much slower rate. However, the uncompressed decoded information at the output of the variable-length decoder requires much more memory in the buffer, which is a significant cost factor for the HDTV set. This is why variable-length decoders are normally used after a rate buffer.
Since there is no peak codeword rate requirement for bit stream decoding before the rate buffer, a relatively slow state machine can be used in front of the rate buffer whose only purpose is to mark the word boundaries of the bit stream. This information can be passed to the variable-length decoder, used after the rate buffer, along with the bit stream, easing its task of word-length computation.
The variable-length decoder arrangement described above significantly improves the speed of operation of the variable length decoder by reducing the propagation delays in its word-length decoding loop. This results in more efficient. implementation of HDTV decoders, particularly, using a single variable-length decoder per system. However, the disadvantage of the above arrangement is that the amount of memory required for tag buffering is substantially equal to the amount of memory required for bit stream buffering before the variable-length decoder. This significantly increases the cost of implementation.